UVa/10819 - Trouble of 13-Dots/#10819.cpp#

   1 #include <iostream>
   2 #include <stdio.h>
   3 using namespace std;
   4
   5 const int MAXN = 100, MAXM = 10205;
   6
   7 int dp[MAXN][MAXM+1], p[MAXN], v[MAXN];
   8
   9 /*
  10   dp[i][j] = Utilizando un subconjunto de los elementos [0..i],
  11   el m�áximo valor que puedo comprar gastando exactamente j pesos.
  12
  13   dp[i][j] == INT_MIN si no puedo escoger un subconjunto de los
  14   elementos [0..i] que valga exactamente j pesos.
  15  */
  16
  17 int main(){
  18   int n, m;
  19   while (scanf("%d %d", &m, &n) == 2){
  20     if (n == 0){
  21       printf("0\n");
  22       continue;
  23     }
  24     int old_m = m;
  25     m += 200;
  26     for (int i=0; i<n; ++i) scanf("%d %d", &p[i], &v[i]);
  27
  28     dp[0][0] = 0;
  29     for (int j=1; j<=m; ++j) dp[0][j] = INT_MIN;
  30     dp[0][p[0]] = v[0];
  31     for (int i=1; i<n; ++i){
  32       for (int j=0; j<=m; ++j){
  33         dp[i][j] = dp[i-1][j];
  34         if (j - p[i] >= 0 && dp[i-1][j-p[i]] >= 0){
  35           dp[i][j] = max(dp[i][j], dp[i-1][j-p[i]] + v[i]);
  36         }
  37       }
  38     }
  39
  40     int ans = 0;
  41     for (int j=0; j<=old_m; ++j){
  42       ans = max(ans, dp[n-1][j]);
  43     }
  44     for (int j=2001; j<=old_m+200; ++j){
  45       ans = max(ans, dp[n-1][j]);
  46     }
  47     printf("%d\n", ans);
  48   }
  49   return 0;
  50 }